023. Merge k Sorted Lists [H]

问题

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Subscribe to see which companies asked this question

思路

这题明显就是Merge two sorted list的升级版，我们知道，那题我们可以用2个指针完成，但是这题，难道要用K个指针？

思路1：每次循环K下，找到每个链表的头，然后把最小的插入新链表中，把这个链表头弃掉，然后重复这个操作。这个最多需要循环KKn次

思路2：二路归并，每次合并两个链表最多合并$log_2N$次

流程：

  • 先每隔2个合并，结果放到合并的第一个链表处
  • 再每隔4个合并，结果放到合并的第一个链表处
    ……
  • 每隔K/2个合并，结果放到合并的第一个链表处

  • 返回第一个链表

    1. //控制每隔多少
    2. for(int step = 1;step < lists.length;step*=2)
    3. //遍历所有可以合并的选项
    4.   for(int i = 0;i < lists.length;i+=step*2)

    假设K= 4：（偶数相对好处理）

  • 先合并L[0],L[1]放到L[0]

  • 然后合并L[2],L[3]放到L[2]
  • 最后合并L[0],L[2]放到L[0]
  • 返回L[0]就好了
    Alt text

假设K=5：(麻烦点，当运行到L[4]的时候它没有下个可以和它合并的元素了，所以应该跳出循环)
Alt text

  1. //控制每隔多少
  2.  for(int step = 1;step < lists.length;step*=2)
  3. //遍历所有可以合并的选项
  4.     for(int i = 0;i < lists.length;i+=step*2)
  5.     {
  6.         //如果某个元素没有下一个元素就退出循环
  7.          if(i+step >= lists.length) break;
  8.          lists[i] = mergeTwoLists(lists[i],lists[i+step]);
  9.     }

所以代码涉及2层循环，外面是控制每隔多少合并一次，里面是遍历所有可以合并的链表，进行合并操作。

  1.  public ListNode mergeKLists(ListNode[] lists) {
  2.         if(lists.length == 0)
  3.             return null;
  4.         //控制每隔多少
  5.         for(int step = 1;step < lists.length;step*=2)
  6.             //遍历所有可以合并的选项
  7.             for(int i = 0;i < lists.length;i+=step*2)
  8.             {
  9.                 //如果某个元素没有下一个元素就退出循环
  10.                 if(i+step >= lists.length) break;
  11.                 lists[i] = mergeTwoLists(lists[i],lists[i+step]);
  12.             }
  13.         return lists[0];
  14.     }
  15.     //完全是之前的代码
  16.     public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
  17.         ListNode result = new ListNode(0);
  18.         ListNode tmp = result;
  19.         while(l1 != null || l2 != null)
  20.         {
  21.             if(l2 == null || (l1 != null && l1.val <= l2.val))
  22.             {
  23.                 tmp.next = l1;
  24.                 l1 = l1.next;
  25.             }
  26.             else 
  27.             {
  28.                 tmp.next = l2;
  29.                 l2 = l2.next;
  30.             }
  31.             tmp = tmp.next;
  32.         }
  33.         return result.next;
  34.     }